package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/check-knight-tour-configuration/">2596. 检查骑士巡视方案</a>
 */
private class Solution2596 {
    private fun checkOK(grid: Array<IntArray>, p: Int, x: Int, y: Int): Boolean {
        if (x < 0 || x >= grid.size || y < 0 || y >= grid.size) {
            return false
        }
        return grid[x][y] == p
    }

    fun checkValidGrid(grid: Array<IntArray>): Boolean {
        if (grid[0][0] != 0) {
            return false
        }
        var p = 1
        var x = 0
        var y = 0
        val step = arrayOf(
            intArrayOf(2, 1),
            intArrayOf(2, -1),
            intArrayOf(-2, 1),
            intArrayOf(-2, -1),
            intArrayOf(1, 2),
            intArrayOf(1, -2),
            intArrayOf(-1, 2),
            intArrayOf(-1, -2),
        )
        while (p < grid.size * grid.size) {
            var ok = false
            for (item in step) {
                if (checkOK(grid, p, x + item[0], y + item[1])) {
                    ok = true
                    x += item[0]
                    y += item[1]
                    p++
                    break
                }
            }
            if (!ok) {
                return false
            }
            println("$p -> $x, $y")
        }
        return true
    }
}

fun main() {
    println(
        Solution2596().checkValidGrid(
            arrayOf(
                intArrayOf(0, 11, 16, 5, 20),
                intArrayOf(17, 4, 19, 10, 15),
                intArrayOf(12, 1, 8, 21, 6),
                intArrayOf(3, 18, 23, 14, 9),
                intArrayOf(24, 13, 2, 7, 22)
            )
        )
    )
}